package com.moyoutian.leetcode;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 148. 排序链表
 * <p>
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 * <p>
 * 进阶：
 * <p>
 * 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：head = [4,2,1,3]
 * <p>
 * 输出：[1,2,3,4]
 * <p>
 * <p>
 * 示例 2：
 * <p>
 * <p>
 * 输入：head = [-1,5,3,4,0]
 * <p>
 * 输出：[-1,0,3,4,5]
 * <p>
 * <p>
 * 示例 3：
 * <p>
 * 输入：head = []
 * <p>
 * 输出：[]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 链表中节点的数目在范围 [0, 5 * 104] 内
 * <p>
 * -105 <= Node.val <= 105
 * <p>
 * 通过次数218,310提交次数327,199
 */
public class Demo148 {


    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args) {

        int[] nums = new int[]{-1, 5, 3, 4, 0};
        ListNode head = null;
        ListNode temp = null;
        for (int num : nums) {
            if (head == null) {
                head = new ListNode(num);
                temp = head;
            } else {
                temp.next = new ListNode(num);
                temp = temp.next;
            }
        }
        ListNode newHead = sortList(head);
        while (newHead != null) {
            System.out.println(newHead.val);
            newHead = newHead.next;
        }
    }

    public static ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode[] hash = new ListNode[200001];
        ListNode temp = head;
        int count = 0;
        while (temp != null) {
            count++;
            int index = temp.val + 100000;
            if (hash[index] != null) {
                ListNode tt = temp.next;
                //如果存在就链接存在结点
                temp.next = hash[index];
                hash[index] = temp;
                temp = tt;
            } else {
                hash[index] = temp;
                temp = temp.next;
                //首次放到该节点，断开关系。保证尾部不与其他相连
                hash[index].next = null;
            }
        }
        int i = 0;
        //查找到头结点
        while (i < hash.length) {
            if (hash[i] != null) {
                temp = hash[i];
                head = temp;
                i++;
                count--;
                break;
            }
            i++;
        }
        //组织结点
        while (i < hash.length && count > 0) {
            if (hash[i] != null) {
                temp.next = hash[i];
                while (temp.next != null) {
                    temp = temp.next;
                    count--;
                }
            }
            i++;
        }

        return head;
    }

    public static ListNode sortList1(ListNode head) {
        if (head == null) {
            return null;
        }
        List<ListNode> listNodeList = new ArrayList<>();
        ListNode temp = head;
        while (temp != null) {
            listNodeList.add(temp);
            temp = temp.next;
        }
        listNodeList.sort(Comparator.comparingInt(o -> o.val));
        head = listNodeList.get(0);
        temp = head;
        for (int i = 1; i < listNodeList.size(); i++) {
            temp.next = listNodeList.get(i);
            temp = temp.next;
        }
        temp.next = null;
        return head;
    }

}
